package _022_2_12

func getOneNumberNum(m *map[int]int, num int) int {
	count := 0
	num2 := num
	for num2 != 0 {
		n, ok := (*m)[num2]
		if ok {
			count += n
			break
		}

		if num2%10 == 1 {
			count++
		}
		num2 /= 10
	}
	(*m)[num] = count
	return count
}

func countDigitOne(n int) int {
	countMap := map[int]int{}
	allOneNumberCount := 0
	for i := 1; i <= n; i++ {
		allOneNumberCount += getOneNumberNum(&countMap, i)
	}

	return allOneNumberCount
}
